import java.util.Arrays;

public class TextDemo {
   public static void heapSort(int[] array){
       builderHeap(array);
       for(int i = array.length-1; i>0; i--){
           swap(array,i,0);
           maxHeapify(array,0,i);
       }
   }
   private static void builderHeap(int[] array){
       for(int i = array.length/2-1; i>=0; i--){
           maxHeapify(array,i,array.length);
       }
   }
   private static void maxHeapify(int[] array,int i,int heapSize){
       int left = 2*i+1;
       int right = left+1;
       int last = i;
       if(left<heapSize && array[left]>array[last]){
           last = left;
       }
       if(right<heapSize && array[right]>array[last]){
           last = right;
       }
       if(last!=i){
           swap(array,last,i);
           maxHeapify(array,last,heapSize);
       }
   }
   public static void shellSort1(int[] array){
      for(int gap = array.length/2; gap>0; gap/=2){
          for(int groupStartIndex = 0;groupStartIndex<gap;groupStartIndex++){
              for(int currentIndex = groupStartIndex+gap;currentIndex<array.length;currentIndex+=gap){
                  int currentNumber = array[currentIndex];
                  int prevIndex = currentIndex-gap;
                  while(prevIndex>=groupStartIndex && currentNumber< array[prevIndex]){
                      array[prevIndex+gap] = array[prevIndex];
                      prevIndex-=gap;
                  }
                  array[prevIndex+gap] = currentNumber;
              }
          }
      }
   }
   public static void shellSort(int[] array){
       for(int gap = array.length; gap>0;gap/=2){
           for(int i = gap;i<array.length;i++){
               int currentNumber = array[i];
               int prevIndex = i-gap;
               while(prevIndex>=0 && array[prevIndex]>currentNumber){
                   array[prevIndex+gap] = array[prevIndex];
                   prevIndex-=gap;
               }
               array[prevIndex+gap] = currentNumber;
           }
       }
   }
   public static void insertSort1(int[] array){
       for(int i = 1;i<array.length;i++){
           int j = i;
           while(j>=1 && array[j-1]>array[j]){
               swap(array,j-1,j);
               j--;
           }
       }
   }
   public static void insertSort(int[] array){
       for(int i = 1;i<array.length;i++){
           int currentNumber = array[i] ;
           int j = i-1;
           while(j>=0 && currentNumber<array[j]){
               array[j+1] = array[j];
               j--;
           }
           array[j+1] = currentNumber;

       }
   }

    public static void selectionSort(int[] array){
        int maxIndex = 0;
        int minIndex = 0;
        for(int i = 0;i<array.length/2;i++){
            maxIndex = i;
            minIndex = i;
            for(int j = i+1;j<array.length-i;j++){
                if(array[j]>array[maxIndex]){
                    maxIndex = j;
                }
                if(array[j]<array[minIndex]){
                    minIndex = j;
                }
            }
            if(minIndex==maxIndex) break;
            swap(array,i,minIndex);
            if(maxIndex==i) maxIndex = minIndex;
            int lastIndex = array.length-i-1;
            swap(array,maxIndex,lastIndex);
        }
    }
    public static void BubbleSort(int[] array){
        int swapIndex = -1;
        int lastIndex = array.length-1;
        boolean flag = true;
        while(flag){
            flag = false;
            for(int i = 0;i<lastIndex;i++){
                if(array[i]>array[i+1]){
                    swap(array,i,i+1);
                    swapIndex = i;
                    flag = true;
                }
            }
            lastIndex = swapIndex;
        }
    }
    public static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }
    public static void main(String[] args) {
        int[] array = new int[]{6,2,4,8,9,1,0,3,5};
        System.out.println(Arrays.toString(array));
        shellSort(array);
        System.out.println(Arrays.toString(array));
        int[] arr = Arrays.copyOf(array,array.length);

    }
}
